home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 2.iso / nt / lkbackup.zip / bits.c next >
C/C++ Source or Header  |  1993-11-03  |  6KB  |  209 lines
  1. /* bits.c -- output variable-length bit strings
  2.  * Copyright (C) 1992-1993 Jean-loup Gailly
  3.  * This is free software; you can redistribute it and/or modify it under the
  4.  * terms of the GNU General Public License, see the file COPYING.
  5.  */
  6.  
  7.  
  8. /*
  9.  *  PURPOSE
  10.  *
  11.  *      Output variable-length bit strings. Compression can be done
  12.  *      to a file or to memory. (The latter is not supported in this version.)
  13.  *
  14.  *  DISCUSSION
  15.  *
  16.  *      The PKZIP "deflate" file format interprets compressed file data
  17.  *      as a sequence of bits.  Multi-bit strings in the file may cross
  18.  *      byte boundaries without restriction.
  19.  *
  20.  *      The first bit of each byte is the low-order bit.
  21.  *
  22.  *      The routines in this file allow a variable-length bit value to
  23.  *      be output right-to-left (useful for literal values). For
  24.  *      left-to-right output (useful for code strings from the tree routines),
  25.  *      the bits must have been reversed first with bi_reverse().
  26.  *
  27.  *      For in-memory compression, the compressed bit stream goes directly
  28.  *      into the requested output buffer. The input data is read in blocks
  29.  *      by the mem_read() function. The buffer is limited to 64K on 16 bit
  30.  *      machines.
  31.  *
  32.  *  INTERFACE
  33.  *
  34.  *      void bi_init (FILE *zipfile)
  35.  *          Initialize the bit string routines.
  36.  *
  37.  *      void send_bits (int value, int length)
  38.  *          Write out a bit string, taking the source bits right to
  39.  *          left.
  40.  *
  41.  *      int bi_reverse (int value, int length)
  42.  *          Reverse the bits of a bit string, taking the source bits left to
  43.  *          right and emitting them right to left.
  44.  *
  45.  *      void bi_windup (void)
  46.  *          Write out any remaining bits in an incomplete byte.
  47.  *
  48.  *      void copy_block(char *buf, unsigned len, int header)
  49.  *          Copy a stored block to the zip file, storing first the length and
  50.  *          its one's complement if requested.
  51.  *
  52.  */
  53.  
  54. #include "tailor.h"
  55. #include "gzip.h"
  56. #include "crypt.h"
  57.  
  58. #ifdef DEBUG
  59. #  include <stdio.h>
  60. #endif
  61.  
  62. #ifdef RCSID
  63. static char rcsid[] = "$Id: bits.c,v 1.24 1993/09/26 04:51:29 ESullivan Exp $";
  64. #endif
  65.  
  66. /* ===========================================================================
  67.  * Local data used by the "bit string" routines.
  68.  */
  69.  
  70. local file_t zfile; /* output gzip file */
  71.  
  72. int unsigned short bi_buf;
  73. /* Output buffer. bits are inserted starting at the bottom (least significant
  74.  * bits).
  75.  */
  76.  
  77. #define Buf_size (8 * 2*sizeof(char))
  78. /* Number of bits used within bi_buf. (bi_buf might be implemented on
  79.  * more than 16 bits on some systems.)
  80.  */
  81.  
  82. int bi_valid;
  83. /* Number of valid bits in bi_buf.  All bits above the last valid bit
  84.  * are always zero.
  85.  */
  86.  
  87. int (*read_buf) OF((char *buf, unsigned size));
  88. /* Current input function. Set to mem_read for in-memory compression */
  89.  
  90. #ifdef DEBUG
  91.   ulg bits_sent;   /* bit length of the compressed data */
  92. #endif
  93.  
  94. /* ===========================================================================
  95.  * Initialize the bit string routines.
  96.  */
  97. void bi_init (zipfile)
  98.     file_t zipfile; /* output zip file, NO_FILE for in-memory compression */
  99. {
  100.     zfile  = zipfile;
  101.     bi_buf = 0;
  102.     bi_valid = 0;
  103. #ifdef DEBUG
  104.     bits_sent = 0L;
  105. #endif
  106.  
  107.     /* Set the defaults for file compression. They are set by memcompress
  108.      * for in-memory compression.
  109.      */
  110.     if (zfile != NO_FILE) {
  111.     read_buf  = file_read;
  112.     }
  113. }
  114.  
  115. /* ===========================================================================
  116.  * Send a value on a given number of bits.
  117.  * IN assertion: length <= 16 and value fits in length bits.
  118.  */
  119.  /* lgk optimize here since this stupid routine has 300K calls in a little
  120.  example make it inline and use registers */
  121. /*  
  122. void _inline send_bits(value, length)
  123.     register int value;  // value to send 
  124.     register int length; // number of bits 
  125. {
  126. #ifdef DEBUG
  127.     Tracev((stderr," l %2d v %4x ", length, value));
  128.     Assert(length > 0 && length <= 15, "invalid length");
  129.     bits_sent += (ulg)length;
  130. #endif
  131.     // If not enough room in bi_buf, use (valid) bits from bi_buf and
  132.     // (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
  133.     // unused bits in value.
  134.      //
  135.     if (bi_valid > (int)Buf_size - length) {
  136.         bi_buf |= (value << bi_valid);
  137.         put_short(bi_buf);
  138.         bi_buf = (ush)value >> (Buf_size - bi_valid);
  139.         bi_valid += length - Buf_size;
  140.     } else {
  141.         bi_buf |= value << bi_valid;
  142.         bi_valid += length;
  143.     }
  144. }
  145. */
  146. /* ===========================================================================
  147.  * Reverse the first len bits of a code, using straightforward code (a faster
  148.  * method would use a table)
  149.  * IN assertion: 1 <= len <= 15
  150.  */
  151. unsigned bi_reverse(code, len)
  152.     unsigned code; /* the value to invert */
  153.     int len;       /* its bit length */
  154. {
  155.     register unsigned res = 0;
  156.     do {
  157.         res |= code & 1;
  158.         code >>= 1, res <<= 1;
  159.     } while (--len > 0);
  160.     return res >> 1;
  161. }
  162.  
  163. /* ===========================================================================
  164.  * Write out any remaining bits in an incomplete byte.
  165.  */
  166. void bi_windup()
  167. {
  168.     if (bi_valid > 8) {
  169.         put_short(bi_buf);
  170.     } else if (bi_valid > 0) {
  171.         put_byte(bi_buf);
  172.     }
  173.     bi_buf = 0;
  174.     bi_valid = 0;
  175. #ifdef DEBUG
  176.     bits_sent = (bits_sent+7) & ~7;
  177. #endif
  178. }
  179.  
  180. /* ===========================================================================
  181.  * Copy a stored block to the zip file, storing first the length and its
  182.  * one's complement if requested.
  183.  */
  184. void copy_block(buf, len, header)
  185.     char     *buf;    /* the input data */
  186.     unsigned len;     /* its length */
  187.     int      header;  /* true if block header must be written */
  188. {
  189.     bi_windup();              /* align on byte boundary */
  190.  
  191.     if (header) {
  192.         put_short((ush)len);   
  193.         put_short((ush)~len);
  194. #ifdef DEBUG
  195.         bits_sent += 2*16;
  196. #endif
  197.     }
  198. #ifdef DEBUG
  199.     bits_sent += (ulg)len<<3;
  200. #endif
  201.     while (len--) {
  202. #ifdef CRYPT
  203.         int t;
  204.     if (key) zencode(*buf, t);
  205. #endif
  206.     put_byte(*buf++);
  207.     }
  208. }
  209.